package com.leetcode.www;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
 *
 * candidates中的每个数字在每个组合中只能使用一次。
 *
 * 注意：解集不能包含重复的组合。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-03-29
 * Time:14:29
 */
public class DFS40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates);//保证重复的元素的都是相邻的,要去重,保证结果里面不能是125,152,只取其中一个即可,也就是刚开始遇到的,然后后面的就跳过了,就不会取到了
        DFS(ret,list,candidates,0,0,target);
        return ret;
    }
    public void DFS(List<List<Integer>> ret,List<Integer> list,int[] candidates,int index,int sum,int target){
        if(sum >= target){
            if(sum == target){
                ret.add(new ArrayList(list));
            }
            return;
        }
        for(int i = index;i < candidates.length;i ++){
            if(candidates[i] > target){
                continue;
            }
            if(i > index && candidates[i] == candidates[i - 1]){//这个去重很关键,不会取到类似于125,152,521这样的重复数据
                continue;
            }
            list.add(candidates[i]);
            DFS(ret,list,candidates,i + 1,sum + candidates[i],target);//此处的i+1表示每个位置上的元素只能使用一次,如果可以重复使用的话就不需要+1
            list.remove(list.size() - 1);
        }
    }

}
